/**
 * Created by liuyaqi on 2017/4/10.
 * 问题描述：给定可选零钱数组smallChanges与需要换成零钱的整钱money，求替换方式有多少种
 * 思路1：
 *      *将money替换成除smallChanges[0]之外的其他零钱的总数
 *      *加上 将money-smallChanges[0]替换成smallChanges中所有零钱的总数
 *      *也就是要么有smallChanges[0]，要么没有smallChanges[0]
 *      这样进行递归可以得到结果
 */

/**
 * 树形递归实现
 * @param money
 * @param smallChanges
 * @returns {*}
 */
function countChange1(money,smallChanges){
    if(smallChanges.length==0)return 0;
    if(money==0)return 1;
    else if(money<0)return 0;

    var smallChangesNew = smallChanges.slice(1);
    return countChange1(money,smallChangesNew)+countChange1(money-smallChanges[0],smallChanges);
}

var smallChanges = [1,5,10,25,50];
console.log(countChange1(100,smallChanges));


//动态规划实现
function change(small,target){
    small = small.sort();
    var table = new Array(target+1);
    for(let i=0;i<table.length;i++){
        table[i] = new Array(small.length);
        for(let j=0;j<table[i].length;j++){
            table[i][j] = 0;
            if(i==small[0])table[i][j] = 1;
        }
    }
    console.log(table);
    //table[i][j] : 使用small[0]到small[j]硬币对i找零种数
    //table[i][j] = table[i][j-1] + table[i-j][j];
    table[small[0]][0] = 1;
    for(let i=small[0]+1;i<=target;i++){
        for(let j=0;j<small.length;j++){
            let current = small[j];

            var x = j-1>=0?table[i][j-1]:0;
            var y = i-current>0?table[i-current][j]:0;
            if(i-current===0)y++;

            table[i][j] = parseInt(x) + parseInt(y);

            console.log("target:",i,j,small,"types:",table[i]);
        }
    }
    return table[target][small.length-1];
}

console.log(change([1,3,5],7));